/*
 * Board.h
 *
 *  Created on: 30-05-2011
 *      Author: chfast
 */

#ifndef SUDOKU_BOARD_INCLUDED
#define SUDOKU_BOARD_INCLUDED

#include <iostream>
#include <bitset>
#include <climits>

namespace util {
#define MID(a, b) ((a+b)/2)
#define POW(a) (a*a)

template<int res, int l = 1, int r = res>
class SQRT;

template<int res, int r>
class SQRT<res, r, r> {
public:
	static const int value = r;
};

template<int res, int l, int r>
class SQRT {
public:
	static const int value = SQRT<res, (POW(MID(r, l)) >= res ? l : MID(r, l)
			+ 1), (POW(MID(r, l)) >= res ? MID(r, l) : r)>::value;
};
}

namespace sudoku {

typedef unsigned long symbol;

class Cell {
public:
	static symbol const INVALID = (sizeof(symbol) * CHAR_BIT - 1);

	Cell() :
		userSymbol(INVALID), correctSymbol(INVALID), fixed(false) {
	}

	operator symbol() const {
		return userSymbol;
	}

	Cell& operator=(symbol sym) {
		userSymbol = sym;
		return *this;
	}

	bool correct() const {
		return userSymbol == correctSymbol;
	}

	bool valid() const {
		return userSymbol != INVALID;
	}

	void reset() {
		userSymbol = INVALID;
	}

	void clear() {
		userSymbol = INVALID;
		fixed = false;
	}

	void fix() {
		fixed = true;
	}

	void save()	{
		correctSymbol = userSymbol;
	}

public:
	symbol userSymbol;
	symbol correctSymbol;
	bool fixed;
};

#define self (*this)

typedef unsigned long bs_t;

template<size_t Rank>
class Board;

template<size_t Rank>
std::ostream& operator<< (std::ostream& os, const Board<Rank>& board);

template<size_t Rank = 9>
class Board {
public:
	static size_t const N = Rank;
	static size_t const G = util::SQRT<Rank>::value;
	static size_t const nCells = Rank * Rank;

	static bs_t const MASK = ~(-1 << Rank);


	Board() {

	}

	Cell& operator()(size_t x, size_t y) {
		return cells[x * Rank + y];
	}

	Cell const& operator()(size_t x, size_t y) const {
		return cells[x * Rank + y];
	}

	Cell& operator[](size_t offset) {
		return cells[offset];
	}

	Cell const& operator[](size_t offset) const {
		return cells[offset];
	}

	void fix() {
		for (Cell* c = cells; c != cells + nCells; ++c) {
			if (c->valid()) {
				c->fix();
			}
		}
	}

	void save() {
		for (Cell* c = cells; c != cells + nCells; ++c) {
			c->save();
		}
	}

	size_t count() {
		size_t count = 0;
		for (Cell* c = cells; c != cells + nCells; ++c) {
			if (c->valid()) {
				++count;
			}
		}
		return count;
	}

	bs_t possibl(size_t offset) {
		bs_t ps = 0;
		for (size_t const* r = rels[offset], *r_end = r + rels.nRels; r != r_end; ++r) {
			ps |= (1 << cells[*r]);
		}
		return ~ps & MASK;
	}

	bs_t possible(size_t offset) {
		const size_t x = offset / Rank;
		const size_t y = offset % Rank;
		register size_t i;
		register size_t j;
		unsigned long ps = 0;

		// row
//		for (j = 0; j < y; ++j)
//			ps[self(x, j)] = 1;
//		for (j = y + 1; j < N; ++j)
//			ps[self(x, j)] = 1;

		const Cell* const cur = cells + offset;
		const Cell* const row_beg = cur - y;
		const Cell* const row_end = row_beg + Rank;
		register const Cell* c = row_beg;
		for (; c != cur; ++c) {
			ps |= (1 << *c);
			//ps[*c] = 1;
		}
		++c;
		for (; c != row_end; ++c) {
			ps |= (1 << *c);
			//ps[*c] = 1;
		}

		// column
//		for (i = 0; i < x; ++i)
//			ps[self(i, y)] = 1;
//		for (i = x + 1; i < N; ++i)
//			ps[self(i, y)] = 1;

		Cell const* const col_beg = cells + y;
		Cell const* const col_end = col_beg + nCells;
		c = col_beg;
		for (; c != cur; c += Rank) {
			ps |= (1 << *c);
		}
		c += Rank;
		for (; c != col_end; c += Rank) {
			ps |= (1 << *c);
		}

		//block
		const size_t b_x = x - (x % G);
		const size_t b_y = y - (y % G);

		for (j = b_y; j < y; ++j) {
			for (i = b_x; i < x; ++i)
				//ps[self(i, j)] = 1;
				ps |= (1 << self(i, j));
			for (i = x + 1; i < b_x + G; ++i)
				ps |= (1 << self(i, j));
		}
		for (j = y + 1; j < b_y + G; ++j) {
			for (i = b_x; i < x; ++i)
				ps |= (1 << self(i, j));
			for (i = x + 1; i < b_x + G; ++i)
				ps |= (1 << self(i, j));
		}
		//bs_t const M = ~(-1 << Rank);
		ps = ~ps & MASK;
		return ps;
	}

private:
	class Rels {
	public:
		static size_t const nRels = G * G + 2 * G * (G - 1) - 1;

		Rels();
		size_t const* operator[](size_t pos) const;

	private:
		static size_t rels[nCells][nRels];
	};

	friend std::ostream& operator<< <>(std::ostream& os, const Board<Rank>& board);

private:
	static Rels const rels;
	Cell cells[nCells];

};

template<size_t Rank>
typename Board<Rank>::Rels const Board<Rank>::rels;

template<size_t Rank>
size_t Board<Rank>::Rels::rels[nCells][nRels];


} // namespace sudoku

#include "Board.impl.h"

#endif // SUDOKU_BOARD_INCLUDED
